package LeetcodeTest_five;
//不同的二叉搜索树
import java.util.ArrayList;
import java.util.List;

public class numTrees
{
    public static void main(String[] args)
    {
        int answer=solution.numTrees(19);
        System.out.println(answer);
    }
}
class solution
{
    public static int numTrees(int n)
    {
        int a[]=new int[n+1];
        int result=backtrace(a,n);
        return result;
    }
    public static int backtrace(int []a,int number)
    {
        int count=0;
        a[0]=1;
        a[1]=1;
        if(a[number]!=0)
            return a[number];
        else
        {
            for (int i = 1; i <=number; i++)
            {
                count += backtrace(a, i-1) * backtrace(a, number - i);
                a[number] = count;
            }
        }
        return a[number];
    }
}